/*public class Test {
}*/
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class NQueens {
    // 存储所有合法方案（每个方案是棋盘的字符串表示）
    private List<List<String>> result = new ArrayList<>();
    // 记录已使用的列
    private Set<Integer> usedCols = new HashSet<>();
    // 记录已使用的正对角线（row - col 为定值）
    private Set<Integer> usedDiag1 = new HashSet<>();
    // 记录已使用的反对角线（row + col 为定值）
    private Set<Integer> usedDiag2 = new HashSet<>();

    public List<List<String>> solveNQueens(int n) {
        // 路径：存储当前每行皇后的列索引（index=行号，value=列号）
        List<Integer> path = new ArrayList<>();
        backtrack(0, n, path);
        return result;
    }

    /**
     * 回溯函数：逐行放置皇后
     * @param row 当前要放置的行号
     * @param n 棋盘大小
     * @param path 记录每行皇后的列索引
     */
    private void backtrack(int row, int n, List<Integer> path) {
        // 终止条件：所有行都放置了皇后（找到一个合法方案）
        if (row == n) {
            result.add(convertToBoard(path, n));
            return;
        }

        // 遍历当前行的所有列，尝试放置皇后
        for (int col = 0; col < n; col++) {
            int diag1 = row - col;
            int diag2 = row + col;

            // 剪枝：如果列或对角线已被占用，跳过当前列
            if (usedCols.contains(col) || usedDiag1.contains(diag1) || usedDiag2.contains(diag2)) {
                continue;
            }

            // 选择：放置皇后，记录占用的列和对角线
            usedCols.add(col);
            usedDiag1.add(diag1);
            usedDiag2.add(diag2);
            path.add(col);

            // 递归：处理下一行
            backtrack(row + 1, n, path);

            // 回溯：撤销选择
            path.remove(path.size() - 1);
            usedDiag2.remove(diag2);
            usedDiag1.remove(diag1);
            usedCols.remove(col);
        }
    }

    /**
     * 将路径（列索引列表）转换为棋盘字符串
     * @param path 每行皇后的列索引
     * @param n 棋盘大小
     * @return 棋盘的字符串表示（每行是 "." 和 "Q" 组成的字符串）
     */
    private List<String> convertToBoard(List<Integer> path, int n) {
        List<String> board = new ArrayList<>();
        for (int col : path) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) {
                sb.append(i == col ? "Q" : ".");
            }
            board.add(sb.toString());
        }
        return board;
    }

    // 测试用例
    public static void main(String[] args) {
        NQueens nQueens = new NQueens();
        int n = 4; // 4皇后问题（共2种解法）
        List<List<String>> solutions = nQueens.solveNQueens(n);
        System.out.println(n + "皇后共有 " + solutions.size() + " 种解法：");
        for (int i = 0; i < solutions.size(); i++) {
            System.out.println("解法 " + (i + 1) + "：");
            solutions.get(i).forEach(System.out::println);
            System.out.println();
        }
    }
}
